package com.wwg.algorithm_data_structures;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description: 如何判断链表是否成环
 * 1. 快慢指针法： 从链表头开始遍历所有节点 判断快慢指针是否有一样的情况
 *
 * 参考：https://www.cnblogs.com/cosefy/p/13070500.html
 *      https://blog.csdn.net/qq_25956141/article/details/79883691
 * @Author: wwg
 * @Date: 2021/8/12
 */

public class HasCycle {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        int pos = 1;
        ListNode head = getLinkedList(list, pos); //调用创建链表方法
        boolean b = hasCycle_Test1(head);    //调用判断链表是否循环的方法
        System.out.println(b);
    }

    public static boolean hasCycle_Test1(ListNode head) {
        if(head==null)
            return false;
        ListNode slow_node = head;
        ListNode fast_node = head;
        while(true){
            if(fast_node.next==null )
                return false;
            if(fast_node.next.next!=null){
                slow_node=slow_node.next;
                fast_node=fast_node.next.next;
            }else{
                return false;
            }
            if(fast_node==slow_node)
                return true;
        }
    }

    public static ListNode getLinkedList(List<Integer> list, int pos) {
        if(pos+1>list.size()) {
            System.out.println("结点个数"+ list.size()+" 插入结点位置： "+pos);
            throw new IllegalArgumentException("非法参数异常");
        }
        if (list.size() == 0)
            return null;
        ListNode first = new ListNode(list.get(0));
        ListNode cur = first;
        for (int i = 0; i < list.size(); i++) {
            if (i == 0)
                continue;
            cur = cur.add(new ListNode(list.get(i))); //添加结点
        }
        if (pos != -1)
            cur.next = getLinkedNode(first, pos);  //将尾结点指向指定位置的结点
        return first;
    }


    public static ListNode getLinkedNode(ListNode head, int pos) {
        int i = 0;
        while (i < pos) {
            i++;
            head = head.next;
        }
        return head;
        //  throw new IllegalArgumentException("非法参数异常");

    }
}
